#ifndef SANDBOX_SDK_UTIL_INTERVAL_TREE_HPP
#define SANDBOX_SDK_UTIL_INTERVAL_TREE_HPP
#include "../details/consexpr.hpp"
#include "../tricks/minmax.hpp"

namespace sandbox
{
	namespace sdk
	{
		namespace detail
		{
			class Object;
			class UpdateQueue;
			
			class Object
			{
				virtual ~Object(){};
			protected:
				Object():m_companion(std::nullptr_t),m_tag(std::numeric_limits<uint32_t>::max()){}
				
				friend class UpdateQueue;
				uint32_t tag()const{return m_tag;}
				void setTag(uint32_t t){m_tag=t;}
				Object * companion()const{return m_companion;}
				void setCompanion(Object* o){m_companion=o;}
			private:
				Object * m_companion;
				uint32_t m_tag;
			};
			class SpatialMap
			{
			};
			class UpdateQueue
			{
			public:
				uint32_t getTime()
				{
					if(m_sequence.empty())
						return std::numeric_limits<uint32_t>::max();
					return m_sequence.front().first;
				}
				Object * get(uint32_t time)
				{
					Object * result=std::nullptr_t;
					do
					{
						if(m_sequence.empty())break;
						if(m_sequence.front().first>time)break;
						//skip moved objects-whose tag does not match time
						if(m_sequence.front().first==m_sequence.second->tag())
						{
							result=m_sequence.front().second;
						}
						std::pop_heap(m_sequence.begin(), 
									  m_sequence.end(),
									  [](const std::pair<uint32_t,Object*>& lhs,
									     const std::pair<uint32_t,Object*>& rhs)
									     {return lhs.first>rhs.first;});
						
						
					}while(!result);
					return result;
				}
				void put2(uint32_t time, Object * a, Object * b, std:vector<Object*>& auxqueue)
				{
					Object * c=a->companion(), *d=b->companion();
					if(c!=std::nullptr_t && c!=b)
					{
						c->setCompanion(std::nullptr_t);
						auxqueue.push(c);
					}
					if(d!=std::nullptr_t && d!=a)
					{
						d->setCompanion(std::nullptr_t);
						auxqueue.push(d);
					}
					
					a->setCompanion(b);
					b->setCompanion(a);
					
					insert(time, a);
					a->setTag(time);
					insert(time, b);
					b->setTag(time);					
				}
				void put1(uint32_t time, Object* a, std:vector<Object*>& auxqueue)
				{
					Object * b=a->companion();
					if(b!=std::nullptr_t){
						//disconnect pair and schedule b
						a->setCompanion(std::nullptr_t);
						b->setCompanion(std::nullptr_t);
						auxqueue.push_back(b);
					}
					insert(time, a);
					a->setTag(time);
				}
				void insert(uint32_t time, Object* obj)
				{
					m_sequence.push_back(make_pair(time, obj));
					std::push_heap(m_sequence.begin(), 
					               m_sequence.end(),
					               [](const std::pair<uint32_t,Object*>& lhs,
					                  const std::pair<uint32_t,Object*>& rhs)
					               {return lhs.first>rhs.first;});
				}
				void erase(Object * obj)
				{
					Object * c;
					if((c=obj->companion())!=std::nullptr_t)
						c->setCompanion(std::nullptr_t);
					size_t nr(0);
					//make sure obj's will be moved to the end of the vector
					for(auto iter : m_sequence)
					{
						if(iter->second==obj)
						{
							iter->first=std::numeric_limits<uint32_t>::max();
							++nr;
						}
					}
					//actually move bad objs to the end
					std::make_heap(m_sequence.begin(), 
					               m_sequence.end(),
					               [](const std::pair<uint32_t,Object*>& lhs,
					                  const std::pair<uint32_t,Object*>& rhs)
					               {return lhs.first>rhs.first;});
					 //painlessly cut the tail
					 m_sequence.resize(m_sequence.size()-nr);
				}
			private:
				std::vector<std::pair<uint32_t,Object*>> m_sequence;
			};
			
		}
		template <class Interval,
				  class Filter,
				  class Tag,
				  class _Allocator=std::Allocator<Object>>
		class IntervalTree
		{
			template <class Interval, class Compare>
			struct Pack 
			{ 
				enum {
					alignment=::sandbox::sdk::detail::min(
						16,
						::sandbox::sdk::detail::next_power_of_2(sizeof(Interval))
					),
				
					allocation_unit=::sandbox::sdk::detail::sizealign(sizeof(Interval), alignment),
					
					block_size=allocation_unit*32,
					
					nodes_per_block=block_size/allocation_unit,
					
					index_shift=::sandbox::sdk::detail::log2(nodes_per_block),
					
					index_mask=index_shift-1
				};
				union {
					Node node;
					unsigned char memory[allocation_unit];
				}m_array[nodes_per_block]; 

				void sort(){
					Node temp;
					//assert number of nodes in block is even
					static_assert((nodes_per_block&1)==0,
							"Rewrite sort algoritm somehow to use it with);
					
					int i=0, max=0;
					while(i<nodes_per_block){
						if(nodes[i].value==null)break;
						if(nodes[i+1]
					}
				}
			};
			
			struct KeyPack 
			{
				Coordinate min, max;
				NodePack * value;
				KeyPack  *
			};

			typedef _Allocator::rebind<NodePack>::other NodeAllocator;			
			typedef _Allocator::rebind<KeyPack>::other  KeyAllocator;			
			
			NodeAllocator m_node_allocator;
			KeyAllocator  m_key_allocator;
			
			void _insert(Coordinate start, Coordinate end, Value val)
			{
				KeyPack * iter=m_head;
				
				
			}
		public:
			typedef unsigned long iterator;
			typedef unsigned long const_iterator;
			
			IntervalTree()
			{}
			template <class allocator_data>
			IntervalTree(allocator_data data):
				m_node_allocator(data),
				m_node_map(data)
			{}
			~IntervalTree()
			{}
			
			template <class T>
			void search(Coordinate min, Coordinate max, Filter filter, T output)
			{
				
			}
		};
		template <class Coordinate,
				  class Compare,
				  class Object,
				  class Allocator=std::Allocator<Object>>
		class TimeIntervalTree
		{
			struct Node {
				Coordinate min, max;
				Object value;
			};
			enum {allocation_unit=detail::next_power_of_2(sizeof(Node))};
			enum {block_size=std::max(4096, allocation_unit*32)};
			enum {nodes_per_block=block_size/allocation_unit};
			enum {index_shift=detail::log2(nodes_per_block)};
			
			
		};
	};
};

#endif // SANDBOX_SDK_UTIL_INTERVAL_TREE_HPP

